/**
 * 归并排序
 *
 * @param {number[]} nums
 * @return {number[]}
 */
function mergeSort(nums) {
  const length = nums.length;
  if (length < 2) {
    return nums;
  }
  const middle = Math.floor(length / 2);
  return merge(mergeSort(nums.slice(0, middle)), mergeSort(nums.slice(middle)));
}

function merge(left, right) {
  const result = [];
  while (left.length && right.length) {
    if (left[0] > right[0]) {
      result.push(right.shift());
    } else {
      result.push(left.shift());
    }
  }
  while (left.length) {
    result.push(left.shift());
  }
  while (right.length) {
    result.push(right.shift());
  }
  return result;
}

const nums = [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48];
console.log(mergeSort(nums));
